package dichotomy.first.bad.version;
/**
 * @Time 2020/1/12
 * @author 王光浩
 * @Need 有一个升序的整型数组，从其中的某一个数开始，后面的所有数字都是符合要求的，系统提供一个方法，可以判断
 *       一个数是否符合要求，请找出这个开始的数。
 *       思路：使用二分法。（通用的二分法）
 *       步骤：使用一个循环进行二分法来查找我们的目标数字，循环结束的条件任然是later>previous，在循环体内部如果mid下标
 *             所表示的数字返回的是true，则将later=mid-1，否则将previous=mid+1。然后返回later即可（但是有一点需要注意如果
 *             target表示的是数字就是最初later所表示的数值，最后later返回的值的将出错）
 *       复杂度分析：O（log2n），空间复杂度O（1）
 */
public class MyMethodTwo {
    public int firstBadVersion(int n) {
    	int later=n;
    	int previous=1;
    	int mid;
    	while(later>=previous) {
    		mid=previous+(later-previous)/2;
    		if(isBadVersion(mid))
    			later=mid-1;
    		else
    			previous=mid+1;
    	}
    	return previous;
    }
    private boolean isBadVersion(int i) {
    	return true;
    }
}
